package org.prism.test;
/**
 * 快速排序
 * 通过一趟排序将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分关键字小，
 * 则分别对这两部分继续进行排序，直到整个序列有序。
 * @author shkstart
 * 2018-12-17
 */
public class QuickSort {
	private static void swap(int[] data, int i, int j) {
		int temp = data[i];
		data[i] = data[j];
		data[j] = temp;
	}

	private static void subSort(int[] data, int start, int end) {
		if (start > end){
			return;
		}
		int key = data[start];
		int low = start;
		int high = end;
		while (low != high){
			while (low < high && data[high] >= key){
				high--;
			}
			while (low < high && data[low] <= key){
				low++;
			}
			if(low < high){
				swap(data,low,high);
			}
		}
		swap(data,start,low);
		subSort(data,start,low-1);
		subSort(data,low+1,end);

	}
	public static void quickSort(int[] data){
		subSort(data,0,data.length-1);
	}
	
	
	public static void main(String[] args) {
		int[] data = { 9, -16, 30, 23, -30, -49, 25, 21, 30 };
		System.out.println("排序之前：\n" + java.util.Arrays.toString(data));
		quickSort(data);
		System.out.println("排序之后：\n" + java.util.Arrays.toString(data));
	}
}